/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.yard42.utils.algorithms;

/**
 *
 * @author Evgen
 */
public class WeightedQuickUnion {

   private int id[];
   private int sz[];

   public WeightedQuickUnion(int N)
   {
      this.id = new int[N];
      this.sz = new int[N];

      for (int i = 0; i < N; i++)
      {
         id[i] = i;
         sz[i] = 1;
      }
   }

   private int root(int i)
   {
      while (i != id[i])
      {
         i = id[i];
      }
      return i;
   }

   public boolean find(int p, int q)
   {
      return root(p) == root(q);
   }

   public void unite(int p, int q)
   {
      int i = root(p);
      int j = root(q);

      if (sz[i] < sz[j])
      {
         id[i] = j;
         sz[j] += sz[i];
      } else
      {
         id[j] = i;
         sz[i] += sz[j];
      }

      sout();
   }

   private void sout()
   {
      for (int i = 0; i < id.length; i++)
      {
         System.out.print(id[i] + " ");
      }

      System.out.println("");
   }

   public int[] getId()
   {
      return id;
   }
}
